第9.6节 对偶性与KKT条件

各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。

本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！

• 9.6.1 广义拉格朗日乘数法
• 9.6.2 原始优化问题
• 9.6.3 对偶优化问题
• 9.6.4 KKT条件
• 9.6.5 计算示例
• 9.6.6 小结
• 引用

9.6 对偶性与KKT条件

在第9.5节内容中，笔者介绍了什么是拉格朗日乘数法及它的作用。同时笔者还特意讲到，拉格朗日乘数法只能用来求解等式约束条件下的极值，但是当约束条件为不等式的时候又该如何进行求解呢？

9.6.1 广义拉格朗日乘数法

由拉格朗日乘数法可知，对于如下等式条件的约束问题

其中是一个维向量。

从式(9.42)可以很明显地看出这是一个含有等式约束条件下的条件极值问题，因此用拉格朗日乘数法就能解决。进一步可构造如下拉格朗日函数

其中是拉格朗日乘子。最后，通过对式子中所有的参数求偏导，令其为0便可求解所有未知变量。

此时，我们接着看如下优化问题

从式(9.44)可以看出，与式(9.42)明显不同的就是在式(9.44)中多了不等式约束条件，因此，为了解决这类问题需要定义如下所示的广义拉格朗日乘数法（Generalized Lagrangian）[1]：

其中，和都是拉格朗日乘子，但接下来的求解过程与之前就大相径庭了。

9.6.2 原始优化问题

根据式(9.44)和式(9.45)考虑如下定义：

式(9.46)表示的含义是求得最大化时和的取值，即和作为自变量与无关，最终求得的结果是关于的函数。 因此，如果原约束条件和均成立，则式(9.46)等价为

则此时有。

同时，我们现在来做这样一个假设，如果存在或 使原约束条件不成立，即 或者，则在这样的条件下会发生什么变化呢？如果，为了最大化，只需取为无穷大，则此时为无穷大，但这样没有意义。同样，如果 ，取为无穷大（与同号），则最后结果同样会无穷大。于是在这种情况下便可以得到。 进一步，结合上述两种情况就可以得到下面这个式子：

再进一步，在满足约束条件的情况下最小化就等同于式(9.44)中所要求解的问题。于是便可以得到如下定义

同时，将式(9.49)称为原始优化问题（Primal Optimization Problem）。

9.6.3 对偶优化问题

接下来继续定义

式(9.50)表示的含义是求得最小化时的取值，即作为自变量（与和无关），最终求得的结果是关于和的函数。

此时便能定义出原问题的对偶问题

并将(9-51)称为对偶优化问题（Dual Optimization Problem）。

可以发现，式(9.49)和式(9.51)的唯一区别就是求解顺序发生了变化，前者是先最大化再最小化，而后者是先最小化然后最大化。 那么原始问题和对偶问题有什么关系呢？为什么又要用对偶问题？通常情况下两者满足以下关系

证明 由式(9.46)和式(9.50)可知，对于任意的有

所以有

进一步根据式(9.54)有

由此便得到了式(9.52)中的不等式。

在上述过程中，之所以要用对偶问题是因为直接对原始问题进行求解异常困难，所以一般会通过将其转换为对偶问题进行求解，但就目前来看，两者并不完全等同，其解也就必然不会相同，所以下面就需要进一步介绍KKT条件。

9.6.4 KKT条件

在9.6.3节中笔者介绍过，要想用对偶问题的解来代替原始问题的解，就必须使两者等价。对于原始问题和对偶问题，假设函数和是凸函数，是仿射函数，并且存在一个，使不等式严格可行（对于所有的都有），则、、同时原始问题和对偶问题解的充分必要条件是、、满足（KarushKuhnTucker,KKT）条件[1]：

其中式(9.58)称为KKT的对偶互补条件（Dual Complementarity Condition）。由此可以得到，如果，则必有，而这一点也将用来说明SVM仅仅只有少数的“支持向量”。同时，需要注意的是KKT条件中计算的是目标函数中的未知数及所有等式约束条件拉格朗日乘子的偏导数。

因此，若存在、、满足上述KKT条件，则、、既是对偶问题的解同样也是原始问题的解。

9.6.5 计算示例

在介绍完对偶问题的相关求解原理后，下面再通过一个示例进行说明。试求解以下优化问题：

由于式(9.61)中的优化问题相对简单，所以可以先通过作图来直观地理解一下，如图9-11所示。

为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！